#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <vector>
#include "../include/radixsort.h"
#include <math.h>

using namespace std;

// 基数排序
// 1、求出最大值的字符串长度（用 abs 取绝对值）
// 2、从低位到高位，依次对每一位进行桶排序
// 3、将桶中的元素依次取出，重新放入数组中
// 4、直到最高位也排序完成

// 时间复杂度：O(dn)  d是字符串的长度,最优、最差都是 O(dn)
// 空间复杂度：O(n)
// 稳定性：稳定


#define BUCKET_SIZE 20

void RadixSort(int arr[], int size) {
    int max = arr[0];
    for (int i = 1; i < size; i++) {
        if (abs(arr[i]) > max)
            max = abs(arr[i]);
    }

    int len = to_string(max).length();
    vector<vector<int>> bucket;

    for (int i = 0; i < len; i++) {
        // 桶排序,为了兼容负数，所以用 20 个桶
        // 由于后面调用了 clear 方法，所以每次排序前都要重新初始化
        bucket.resize(BUCKET_SIZE);
        for (int j = 0; j < size; j++) {
            int num = ((arr[j] / (int)pow(10, i)) % 10 + 10);
            bucket[num].push_back(arr[j]);
        }

        int index = 0;
        for (int j = 0; j < BUCKET_SIZE; j++) {
            for (int k = 0; k < bucket[j].size(); k++) {
                arr[index++] = bucket[j][k];
            }
        }
        bucket.clear();
    }
}

// int main(int argc, const char** argv) {
//     int arr[10];
//     srand(time(NULL));
//     for (int i = 0; i < 10; i++) {
//         arr[i] = rand() % 100;
//         cout << arr[i] << " ";
//     }
//     arr[5] = -100;
//     arr[3] = -80;
//     arr[6] = -99;
//     cout << endl;

//     RadixSort(arr, 10);
//     for (int val : arr)
//         cout << val << " ";
//     cout << endl;
//     return 0;
// }